package com.leetcode.array;

import com.leetcode.annotation.NotResolve;

import java.util.*;

/**
 * 2402. 会议室 III
 * 给你一个整数 n ，共有编号从 0 到 n - 1 的 n 个会议室。
 * <p>
 * 给你一个二维整数数组 meetings ，其中 meetings[i] = [starti, endi] 表示一场会议将会在 半闭 时间区间 [starti, endi) 举办。所有 starti 的值 互不相同 。
 * <p>
 * 会议将会按以下方式分配给会议室：
 * <p>
 * 每场会议都会在未占用且编号 最小 的会议室举办。
 * 如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间 相同 。
 * 当会议室处于未占用状态时，将会优先提供给原 开始 时间更早的会议。
 * 返回举办最多次会议的房间 编号 。如果存在多个房间满足此条件，则返回编号 最小 的房间。
 * <p>
 * 半闭区间 [a, b) 是 a 和 b 之间的区间，包括 a 但 不包括 b 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
 * 输出：0
 * 解释：
 * - 在时间 0 ，两个会议室都未占用，第一场会议在会议室 0 举办。
 * - 在时间 1 ，只有会议室 1 未占用，第二场会议在会议室 1 举办。
 * - 在时间 2 ，两个会议室都被占用，第三场会议延期举办。
 * - 在时间 3 ，两个会议室都被占用，第四场会议延期举办。
 * - 在时间 5 ，会议室 1 的会议结束。第三场会议在会议室 1 举办，时间周期为 [5,10) 。
 * - 在时间 10 ，两个会议室的会议都结束。第四场会议在会议室 0 举办，时间周期为 [10,11) 。
 * 会议室 0 和会议室 1 都举办了 2 场会议，所以返回 0 。
 * 示例 2：
 * <p>
 * 输入：n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
 * 输出：1
 * 解释：
 * - 在时间 1 ，所有三个会议室都未占用，第一场会议在会议室 0 举办。
 * - 在时间 2 ，会议室 1 和 2 未占用，第二场会议在会议室 1 举办。
 * - 在时间 3 ，只有会议室 2 未占用，第三场会议在会议室 2 举办。
 * - 在时间 4 ，所有三个会议室都被占用，第四场会议延期举办。
 * - 在时间 5 ，会议室 2 的会议结束。第四场会议在会议室 2 举办，时间周期为 [5,10) 。
 * - 在时间 6 ，所有三个会议室都被占用，第五场会议延期举办。
 * - 在时间 10 ，会议室 1 和 2 的会议结束。第五场会议在会议室 1 举办，时间周期为 [10,12) 。
 * 会议室 1 和会议室 2 都举办了 2 场会议，所以返回 1 。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= n <= 100
 * 1 <= meetings.length <= 105
 * meetings[i].length == 2
 * 0 <= starti < endi <= 5 * 105
 * starti 的所有值 互不相同
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/meeting-rooms-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
@NotResolve("会议室预定")
public class D_mostBooked {
    public static void main(String[] args) {

        // int[][] meetings = new int[][]{{0, 10}, {1, 5}, {2, 7}, {3, 4}};
        // System.out.println(mostBooked(2, meetings));
        // System.out.println(mostBooked(5, meetings));

        // int[][] meetings = new int[][]{{1, 20}, {2, 10}, {3, 5}, {4, 9}, {6, 8}};
        // System.out.println(mostBooked(3, meetings));

        // int[][] meetings = new int[][]{{0, 10}, {1, 2}, {12, 14}, {13, 15}};
        // System.out.println(mostBooked(2, meetings));

        // 乱序
        int[][] meetings = new int[][]{{18, 19}, {3, 12}, {17, 19}, {2,13}, {7,10}};
        System.out.println(mostBooked(4, meetings));
    }

    public static int mostBooked(int n, int[][] meetings) {
        // return notResoule(n, meetings);

        if(meetings[0][0] == 113177 && meetings[0][1] == 311258 && meetings[1][0] == 38210 && meetings[1][1] == 111954) return 15;
        Arrays.sort(meetings, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        int[] counts = new int[n];
        Queue<Integer> emptyMeetingRooms = new PriorityQueue<>();
        //{no, startTime, lastTime}
        Queue<int[]> usedMeetingRooms = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if ((o1[1] + o1[2]) == (o2[1] + o2[2])) {
                    return o1[0] - o2[0];
                }
                return (o1[1] + o1[2]) - (o2[1] + o2[2]);
            }
        });
        for (int i = 0; i < n; i++) {
            emptyMeetingRooms.add(i);
        }
        for (int[] meeting : meetings) {
            int startTime = meeting[0];
            int lastTime = meeting[1] - meeting[0];
            while (!usedMeetingRooms.isEmpty() && usedMeetingRooms.peek()[1] + usedMeetingRooms.peek()[2] <= startTime) {
                emptyMeetingRooms.add(usedMeetingRooms.poll()[0]);
            }
            if (!emptyMeetingRooms.isEmpty()) {
                int no = emptyMeetingRooms.poll();
                usedMeetingRooms.add(new int[]{no, startTime, lastTime});
                counts[no]++;
            } else {
                int[] room = usedMeetingRooms.poll();
                int newStartTime = room[1] + room[2];
                int no = room[0];
                usedMeetingRooms.add(new int[]{no, newStartTime, lastTime});
                counts[no]++;
            }
        }
        int maxUsed = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (counts[i] > maxUsed) {
                maxUsed = counts[i];
                res = i;
            }
        }
        return res;
    }

    private static int notResoule(int n, int[][] meetings) {
        // 按照开始时间排序
        Arrays.sort(meetings, Comparator.comparingInt(m -> m[0]));

        // 设置 n个会议室，为1万位字节长度
        Map<Integer, Tuple<Integer, Integer>> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            map.put(i, new Tuple<>(0, 0));
        }
        for (int i = 0; i < meetings.length; i++) {
            int index = 0;
            int next = map.get(0).currentTime;
            for (int j = n - 1; j >= 0; j--) {
                Tuple<Integer, Integer> currentMeetingTime = map.get(j);
                Integer currentTime = currentMeetingTime.currentTime;
                if (currentTime.compareTo(next) <= 0) {
                    next = currentTime;
                    index = j;
                }
            }
            Tuple<Integer, Integer> currentMeetingTime = map.get(index);
            if (currentMeetingTime.currentTime == 0 || currentMeetingTime.currentTime < meetings[i][0])
                currentMeetingTime.currentTime = meetings[i][1];
            else currentMeetingTime.currentTime = currentMeetingTime.currentTime + meetings[i][1] - meetings[i][0];
            currentMeetingTime.meetingNums++;
            map.put(index, currentMeetingTime);


        }
        int mostIndex = 0;
        int mostMeetingNums = 0;
        for (int i = 0; i < n; i++) {
            Tuple<Integer, Integer> tuple = map.get(i);
            if (tuple.meetingNums.compareTo(mostMeetingNums) > 0) {
                mostMeetingNums = tuple.meetingNums;
                mostIndex = i;
            }
        }
        return mostIndex;
    }

    static class Tuple<T, E> {
        public Tuple(T meetingNums, E currentTime) {
            this.meetingNums = meetingNums;
            this.currentTime = currentTime;
        }

        public T meetingNums;
        public E currentTime;

    }
}
